/***************************************************************************************************
 *Copyright(C),2010-2016,Sumscope
 *FileName	:  pinyin_search_idvec.cpp
 *Author	:  scofined.qi
 *Version	:  1.0
 *Date		:  2017/06/04
 *Desc		:  //用于主要说明此程序文件完成的主要功能
 *Relation :
 *Others	:  //其他内容说明
 *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
 *History	:
 * //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
 ***************************************************************************************************/
#include "pinyin_search_idvec.h"

#include "pinyin_search_idstore.h"
#include "pinyin_search_set.h"

#ifndef BASSERTS
#define BASSERTS  //
#endif
#ifndef BASSERT
#define BASSERT  //
#endif

namespace qb {
namespace base {
using namespace spell;
#define FIND_AFTER(RET, KEY, POS)                  \
  {                                                \
    int temp = find_fast(KEY, POS);                \
    RET = temp >= 0 ? temp : find_slow2(KEY, POS); \
  }
// #define FIND_AFTER(RET,KEY,POS) RET = find_after_old(KEY,POS)

namespace internal {
IndexIdVec::IndexIdVec() : m_first(0), m_count(0), m_capcity(0) {}

IndexIdVec::IndexIdVec(IndexId* first, int count, int capcity) {
  bind(first, count, capcity);
}

void IndexIdVec::bind(IndexId* first, int count, int capcity) {
  m_first = first;
  m_count = count;
  m_capcity = capcity;
}

void IndexIdVec::copyfrom(const IndexIdVec& iivec) {
  memcpy(m_first, iivec.m_first, sizeof(IndexId) * m_count);
}

void IndexIdVec::copyfrom(const InverseSet& iset) {
  // BASSERT(m_first && m_capcity >= iset.size());
  m_count = 0;
  for (InverseSet::const_iterator it = iset.cbegin(); it != iset.cend(); ++it) {
    m_first[m_count++] = makeid(it->first, it->second);
  }
}

void IndexIdVec::copyto(InverseSet& iset) {
  iset.reset();
  for (int i = 0; i < m_count; i++) iset.add(getkey(m_first[i]));
}
bool IndexIdVec::equal(const InverseSet& iset) const {
  if (m_count != iset.size()) return false;
  if (m_count > 0 && m_first == NULL) return false;
  int i = 0;
  for (InverseSet::const_iterator it = iset.cbegin();
       i < m_count && it != iset.cend(); ++it, ++i) {
    IndexId id = makeid(it->first, it->second);
    if (id != m_first[i]) return false;
  }
  return true;
}
IndexIdVec::~IndexIdVec() {}

bool IndexIdVec::add(int key) {
  // BASSERT(m_first && m_capcity > 0);
  int ipos = 0;
  FIND_AFTER(ipos, key, 0);
  // BASSERT(ipos >= 0 && ipos <= m_count);
  IndexId* pid = m_first + ipos;
  if (ipos >= 0 && ipos < m_count) {
    if (getkey(*pid) == key) {
      *pid = makeid(key, getval(*pid) + 1);
      return true;
    }
  }

  // 将ipos后面的往后移动一个位置
  if (m_count >= m_capcity) return false;

  if (m_count > ipos)
    memmove(m_first + ipos + 1, m_first + ipos,
            (m_count - ipos) * sizeof(IndexId));
  *pid = makeid(key, 1);
  m_count++;
  return true;
}

void IndexIdVec::remove(int key) {
  int ipos = 0;
  FIND_AFTER(ipos, key, 0);
  if (ipos >= 0 && ipos < m_count) {
    IndexId* pid = m_first + ipos;
    if (getkey(*pid) != key) return;
    *pid = makeid(key, getval(*pid) - 1);
    if (getval(*pid) <= 0) {
      // 将后面的向前移动
      IndexId* dest = m_first + ipos;
      IndexId* source = m_first + ipos + 1;
      IndexId* end = m_first + m_count;
      // for (; source < end;)
      //	*dest++ = *source++;
      if (m_count > ipos + 1)
        memmove(dest, source, sizeof(IndexId) * (m_count - ipos - 1));
      m_count--;
    }
  }
}
void IndexIdVec::check() {
  if (m_first && m_count > 0) {
    int nerror = 0;
    int last = getkey(*m_first);
    for (int i = 1; i < m_count; i++) {
      if (last >= getkey(m_first[i])) nerror++;
      last = getkey(m_first[i]);
    }
    BASSERTS(nerror <= 0, "nerror=%d", nerror);
  }
}
bool IndexIdVec::exist(int key) const {
  int ipos = 0;
  FIND_AFTER(ipos, key, 0);
  if (ipos < 0 || ipos >= m_count) return false;
  return getkey(m_first[ipos]) == key;
}

void IndexIdVec::clear() {
  if (m_first) m_first[0] = 0;
  m_count = 0;
}
void IndexIdVec::intersect(const InverseSet& iset) {
  int npos = 0;
  int ncount = 0;
  if (m_count <= iset.size()) {
    for (int i = 0; i < m_count; i++) {
      int key = spell::getkey(m_first[i]);
      npos = iset.find(key, npos);
      if (npos >= iset.size()) break;
      if (iset.at(npos).getkey() == key)
        m_first[ncount++] = spell::makeid(key, iset.at(i).getval());
    }
  } else {
    for (int i = 0; i < iset.size(); i++) {
      int key = iset.at(i).getkey();
      npos = find_after(key, npos);
      if (npos >= m_count) break;
      if (key == spell::getkey(m_first[npos]))
        m_first[ncount++] = spell::makeid(key, iset.at(i).getval());
    }
  }
  if (0) {
    for (int i = 0; i < m_count; i++) {
      if (iset.exist(getkey(m_first[i]))) {
        m_first[ncount++] = m_first[i];
      }
    }
  }
  m_count = ncount;
  if (m_count < m_capcity && m_first) m_first[m_count] = 0;
}
void IndexIdVec::intersect(const IndexIdVec& iis) {
  // 如果自身比iis要大,那么取小的作为待遍历的容器
  // 取大的作为搜索容器,这样做,减少查询次数,略微提升性能18%
  // 改进算法,使用find_after,单项测试提升3倍,整体提升1倍
  intersect_old(iis);
  return;
  int ncount = 0, npos = 0;
  bool larger = size() > iis.size();
  int nloop = larger ? iis.size() : size();
  int nmaxpos = larger ? size() : iis.size();
  const IndexId* first = larger ? iis.m_first : m_first;
  const IndexIdVec* search = larger ? this : &iis;
  int ki = 0;

  for (int i = 0; i < nloop; i++) {
    ki = spell::getkey(first[i]);
    // ret = (const Value*)bsearch(&ki, search->m_first, search->size(),
    // sizeof(int), KeyCompare::CompByKey);

    // npos = npos; //search->find_after(ki, npos);
    // FIND_AFTER(npos, ki, npos);
    int temp = search->find_after(ki, npos);
    if (temp >= nmaxpos) break;
    if (getkey(search->m_first[temp]) == ki) m_first[ncount++] = first[i];
    npos = temp + 1;
  }

  m_count = ncount;
  if (m_count < m_capcity && m_first) m_first[m_count] = 0;
  return;
}
void IndexIdVec::intersect_old(const IndexIdVec& iis) {
  check();
  (const_cast<IndexIdVec*>(&iis))->check();
  int ncount = 0;
  for (int i = 0; i < m_count; i++) {
    if (iis.exist(getkey(m_first[i]))) {
      m_first[ncount++] = m_first[i];
    }
  }
  m_count = ncount;
  if (m_capcity > m_count)
    memset(m_first + m_count, 0, (m_capcity - m_count) * sizeof(IndexId));
}
void IndexIdVec::transform() {
  if (m_first) {
    for (int i = 0; i < m_count; i++) {
      m_first[i] = getkey(m_first[i]);
    }
  }
}

bool IndexIdVec::get(int index, KeyType& key, CountType& val) const {
  if (index >= 0 && index < m_count && m_first) {
    key = spell::getkey(m_first[index]);
    val = spell::getval(m_first[index]);
    return true;
  }
  key = val = 0;
  return false;
}
int IndexIdVec::find_slow2(int key, int npos) const {
  // 从npos开始查找第一个=key的位置,返回-1表示找不到
  int left = npos, right = m_count - 1, mid = 0;
  int kl, kr, km, step;
  kl = getkey(m_first[left]);
  right = left + (key - kl);
  if (right >= m_count - 1) right = m_count - 1;
  kr = getkey(m_first[right]);
  BASSERT(kr >= key);
  int gap = 16;  // 经过大量测试,16效果最佳
  int i = -1;
  while (left + gap < right) {
    // 二分法:step = (right - left) >> 1;
    // 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
    // 经过测试,真实11w债券数据,比例法性能是二分法的2倍
    step = (int)(1.0 * (right - left) * (key - kl) / (kr - kl));
    mid = left + (step < 1 ? gap : step);
    km = getkey(m_first[mid]);
    if (key == km) {
      i = mid;
      break;
    }
    if (key < km) {
      right = mid;
      kr = getkey(m_first[right]);
    } else {
      left = mid + 1;
      kl = getkey(m_first[left]);
    }
  }
  if (i < 0) {
    i = left;
    for (; i <= right; i++) {
      if (key <= getkey(m_first[i])) break;
    }
  }

  BASSERT(i < m_count && getkey(m_first[i]) >= key);
  BASSERT(i == 0 || getkey(m_first[i - 1]) < key);
  return i;
}
int IndexIdVec::find_slow(int key, int npos) const {
  // return find_after_new(key, npos);
  //  从npos开始查找第一个>=key的位置,返回-1表示找不到
  int left = npos, right = m_count - 1, mid = 0;
  int kl, kr, km, step;
  kl = getkey(m_first[left]);
  kr = getkey(m_first[right]);
  const int gap = 16;  // 经过大量测试,16效果最佳
  int i = -1;
  while (left + gap < right) {
    // 二分法:step = (right - left) >> 1;
    // 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
    // 经过测试,真实11w债券数据,比例法性能是二分法的2倍
    step = (int)(1.0 * (right - left) * (key - kl) / (kr - kl));
    mid = left + (step < 1 ? gap : step);
    km = getkey(m_first[mid]);
    if (key == km) {
      i = mid;
      break;
    }
    if (key < km) {
      right = mid;
      kr = getkey(m_first[right]);
    } else {
      left = mid + 1;
      kl = getkey(m_first[left]);
    }
  }
  if (i < 0) {
    i = left;
    for (; i <= right; i++) {
      if (key <= getkey(m_first[i])) break;
    }
  }

  BASSERT(i < m_count && getkey(m_first[i]) >= key);
  BASSERT(i == 0 || getkey(m_first[i - 1]) < key);
  return i;
}
int IndexIdVec::find_after(int key, int npos) const {
  // return find_after_new(key, npos);
  //  从npos开始查找第一个>=key的位置,返回-1表示找不到
  int pos = find_fast(key, npos);
  if (pos < 0) pos = find_slow(key, npos);
  return pos;
}
int IndexIdVec::find_after_old(int key, int npos) const {
  if (npos < 0 || m_first == nullptr || npos >= m_count) return m_count;
  if (key <= spell::getkey(m_first[npos])) return npos;
  if (m_count >= 1) {
    int last = spell::getkey(m_first[m_count - 1]);
    if (key > last) return m_count;
    // if (key == last)return m_count - 1;
  }
  int left = npos, right = m_count - 1, mid = 0;
  int kl, kr, km, step;
  kl = getkey(m_first[left]);
  kr = getkey(m_first[right]);
  int gap = 16;  // 经过大量测试,16效果最佳
  int i = -1;
  while (left + gap < right) {
    // 二分法:step = (right - left) >> 1;
    // 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
    // 经过测试,真实11w债券数据,比例法性能是二分法的2倍
    step = (int)(1.0 * (right - left) * (key - kl) / (kr - kl));
    mid = left + (step < 1 ? gap : step);
    km = getkey(m_first[mid]);
    if (key == km) {
      i = mid;
      break;
    }
    if (key < km) {
      right = mid;
      kr = getkey(m_first[right]);
    } else {
      left = mid + 1;
      kl = getkey(m_first[left]);
    }
  }
  if (i < 0) {
    i = left;
    for (; i <= right; i++) {
      if (key <= getkey(m_first[i])) break;
    }
  }

  BASSERT(i < m_count && getkey(m_first[i]) >= key);
  BASSERT(i == 0 || getkey(m_first[i - 1]) < key);
  return i;
}
int IndexIdVec::find(int key) const {
  // BASSERT(m_first);
  if (m_count <= 0 || key <= getkey(m_first[0])) return 0;
  if (key > getkey(m_first[m_count - 1])) return m_count;

  int left = 0, right = m_count, mid = 0;
  while (left + 4 < right) {
    mid = (left + right) >> 1;
    if (key < getkey(m_first[mid]))
      right = mid;
    else
      left = mid;
  }

  int i = left;
  for (; i < right; i++) {
    if (key <= getkey(m_first[i])) break;
  }
  return i;
}

}  // namespace internal
}  // namespace base
}  // namespace qb
